#define _CRT_SECURE_NO_WARNINGS 1

  struct ListNode {
 	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
  };
 
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == nullptr && pHead2 == nullptr) return nullptr;
        if (pHead1 == nullptr && pHead2 != nullptr) return pHead2;
        if (pHead1 != nullptr && pHead2 == nullptr) return pHead1;
        ListNode* ret = pHead1;
        ListNode* cur1 = pHead1;
        ListNode* cur2 = pHead2;
        if (pHead1->val > pHead2->val)
        {
            cur1 = pHead2;
            cur2 = pHead1;
            ret = pHead2;
        }
        while (cur1 && cur2)
        {
            if (cur1->next == nullptr) break;
            if (cur2->val <= cur1->next->val)
            {
                ListNode* tmp = cur2->next;
                cur2->next = cur1->next;
                cur1->next = cur2;
                cur2 = tmp;
            }
            else
            {
                cur1 = cur1->next;
            }
        }
        if (cur2) cur1->next = cur2;
        return ret;
    }
};